Skip to content

Leetcode 41. First Missing Positive 题解

题目链接

Leetcode 41. First Missing Positive

题目内容

Given an unsorted integer array, find the smallest missing positive integer.

Example1: Input: [1,2,0] Output: 3

Example2: Input: [3,4,-1,1] Output: 2

Example2: Input: [7,8,9,11,12] Output: 1

Note: Your algorithm should run in O(n) time and uses constant extra space.

解题思路

这题目其实想明白了还是十分简单的，题目的意思就是要我们找到没有在输入的Vector中出现的最小的正数，这题要求我们在O(n)的时间内使用常数的额外空间来解决。首先想到的就是排序，但是显然排序 是不可能在O(n)时间内解决这个问题的，但是我从排序算法中最快的桶排序Bucket Sort中找到了灵感，桶排序的缺点就是空间消耗过大，但是若其应用在我们的这个题目中，我们无需多余的空间去存放超出我们index的数字，超出index的数字我们直接放在原处。具体的做法就是，先扫描一遍我们的输入Vector，如果某个元素在1~size之间，则把它放入Vector中对应的i-1位置，即交换两元素的位置。最后再扫描Vector一遍，找到第一个满足Vector[i] != i+1的数，我们就可以找到第一个缺失的正数了，若是扫描Vector发现全部符合，则意味着1~size之间的数全被包含在Vector中，最小的缺失正数为size+1。

时间复杂度为O(n),Detail如下 dt

题目代码

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        int i = 0;
        while (i < n)
            if (nums[i] > 0 && nums[i] <= nums.size() && nums[nums[i] - 1] != nums[i]) //nums[nums[i] - 1] != nums[i]防止不断交换
                swap(nums[i], nums[nums[i] - 1]);
            else
                i++;

        for(int i = 0; i < n; ++i)
            if(nums[i] != i + 1)
                return i + 1;

        return n + 1;
    }
};